/*
Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2.

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
*/
string multiply(string num1, string num2) 
{
        int m=num1.size();
        int n=num2.size();
        reverse(num1.begin(), num1.end());
        reverse(num2.begin(), num2.end());
        vector<int>ret(m+n);
        for(int i=0; i<m; i++)
        {
            for(int j=0;j<n; ++j)
            {
                ret[i+j] += (num1[i]-'0')*(num2[j]-'0');
            }
        }
      for(int k=0; k<m+n; ++k)  
      {
          if(ret[k] >= 10 )
          {
              ret[k+1] += ret[k]/10;
              ret[k] %= 10; 
          }
      }
        int l=n+m-1;
        while(l>=0 && ret[l]==0)--l;
        if(l<0)return "0";
        string s;
        while(l>=0)
        {
            s += ret[l--]+'0';
        }
        return s;
    }